home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3070 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: Rezonet.net!news
  2. From: ray@ultimate-tech.com (Ray Dunn)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Fastest way to computer log(base2) of x?
  5. Date: 25 Jan 1996 21:02:28 GMT
  6. Organization: Ultimate Technographics Inc.
  7. Message-ID: <4e8r54$n8q@ns.RezoNet.NET>
  8. References: <4e61iu$p6e@villa.fc.net> <4e6p7t$1n72@cymbal.aix.calpoly.edu>
  9. NNTP-Posting-Host: 204.19.230.7
  10. Mime-Version: 1.0
  11. Content-Type: Text/Plain; charset=US-ASCII
  12. X-Newsreader: WinVN 0.99.7
  13.  
  14. In referenced article, Dan Stubbs says...
  15. >It seems like an interesting exercise to find the left bit using
  16. >a binary search since moving an appropriate mask around (for
  17. >speed) is a bit "different."  The following is for 32 bit ints,
  18. >as you can see it is simple to modify for any width int that is
  19. >a power of 2.
  20. >
  21. >/*------------------------------------------------------------------*/
  22. >int  left_most_bit (int k) {
  23. >/*   
  24. > *   returns the position of the left most bit in k assuming that
  25. > *      k != 0 and 32 bit ints. The algorithm used is essentially a
  26. > *      binary search.
  27. > */
  28. >   int posn = 0, width = 16, mask = 0xffff0000;
  29. >
  30. >   while (width > 1) {
  31. >      if (k & mask) {
  32. >         width /= 2;
  33. >         mask <<= (posn + width);
  34. >         mask >>=  posn;
  35. >      }
  36. >      else {
  37. >         mask >>= width;
  38. >         posn +=  width;
  39. >      }
  40. >   } 
  41. >   if (k & mask) return posn;
  42. >   else return posn+1;
  43. >}
  44.  
  45. I'm sorry, but there are an unreasonable number of errors in this 
  46. code.  It's difficult to even see what you're trying to do, let alone 
  47. correct things like mask should be of unsigned type, and a possible 
  48. reliance on right shift inserting zeros.  Please compile and test 
  49. before posting.
  50.  
  51. [emailed and posted]
  52. -- 
  53. Ray Dunn (opinions are my own) | Phone: (514) 938 9050
  54. Montreal                       | Phax : (514) 938 5225
  55. ray@ultimate-tech.com          | Home : (514) 630 3749
  56.  
  57.